1229. Meeting Scheduler
Medium

Given the availability time slots arrays slots1 and slots2 of two people and a meeting duration duration, return the earliest time slot that works for both of them and is of duration duration.

If there is no common time slot that satisfies the requirements, return an empty array.

The format of a time slot is an array of two elements [start, end] representing an inclusive time range from start to end.

It is guaranteed that no two availability slots of the same person intersect with each other. That is, for any two time slots [start1, end1] and [start2, end2] of the same person, either start1 > end2 or start2 > end1.

 

Example 1:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]

Example 2:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12
Output: []

 

Constraints:

  • 1 <= slots1.length, slots2.length <= 104
  • slots1[i].length, slots2[i].length == 2
  • slots1[i][0] < slots1[i][1]
  • slots2[i][0] < slots2[i][1]
  • 0 <= slots1[i][j], slots2[i][j] <= 109
  • 1 <= duration <= 106
Accepted
34,181
Submissions
62,637
Seen this question in a real interview before?
Companies
Show Hint 1
Assume that in the solution, the selected slot from slotsA is bigger than the respectively selected slot from slotsB.
Show Hint 2
Use two pointers in order to try all the possible intersections, and check the length.
Show Hint 3
Do the same in step N° 1 but now assume that the selected slot from slotsB is bigger, return the minimum of the two options.

Average Rating: 5.00 (15 votes)

Premium

Solution


Overview

To find the earliest time slot that works for both the people, the most straightforward approach would be to examine all possible time slots for them. To improve it, we can either sort both input arrays and apply two pointers, or we can use a heap for sorting the time slots and find the earliest overlapping time slot. We will cover both of these approaches in this article.



Approach 1: Two pointers

Intuition

The common slot between two slots.

Figure 1. The common slot between two slots.

We want to sort both slots1 and slots2 by the start time first, then initialize two pointers, each of which points to the beginning of the two arrays. From there, we will compare the two slots, and move one pointer at a time if the common slot is smaller than duration.

Note that sorting by the start time vs the end time is the same, this is because, if a time slot starts earlier, it will end earlier. Remember that for both people, there're no overlapping time slots

Here comes the question: how do we decide which pointer should be incremented?

The answer is: we will always move the one that ends earlier. Assuming that we are comparing slots1[i] and slots2[j] and slots1[i][1] > slots2[j][1], we would always choose to move the pointer j. The reason is that, as both slots are sorted, if slots1[i][1] > slots2[j][1], we know slots1[i+1][0] > slots2[j][1] so that there will be no intersection between slots1[i+1] and slots2[j].

Always move the one that ends earlier.

Figure 2. Always move the one that ends earlier.

Algorithm

  • Sort both slots1 and slots2 by the start time.
  • Initialize two pointers, pointer1 and pointer2, pointing to the beginning of slots1 and the beginning of slots2 respectively.
  • Iterate until pointer1 reaches the end of slots1 or pointer2 reaches the end of slots2:
    • Find the common slot of slots1[pointer1] and slots2[pointer2].
    • If the common slot is greater than or equal to duration, return the result.
    • Else, find the slot that ends earlier and move the pointer.
  • If no common slot is found, return an empty array.

Implementation

Complexity Analysis

  • Time complexity: O(MlogM+NlogN)O(M \log M + N \log N), when MM is the length of slots1 and NN is the length of slots2.

    Sorting both arrays would take O(MlogM+NlogN)O(M \log M + N \log N). The two pointers take O(M+N)O(M + N) because, during each iteration, we would visit a new element, and there are a total of M+NM+N elements. Putting these together, the total time complexity is O(MlogM+NlogN)O(M \log M + N \log N).

  • Space complexity: O(1)O(1). This is because we do not use any additional data structures; we only use a few fixed-size integer variables.



Approach 2: Heap

Intuition

Another approach of systematically selecting slots and comparing them is using a heap. We would initialize a heap timeslots and push all of the time slots into it.

The key idea here is that we only need one heap. That is, we can put the time slots for both people into the same heap, and then if we find a common time slot, we know that the two-time slots couldn't possibly be for the same person. Before reading the justification for this, have a think for yourself about why we can draw such a bold conclusion.

The problem description states that the time slots for a single person do not overlap. This means that if, for example, we have the time slots [10, 15] and [14, 20], then we know that these time slots cannot be for the same person. Otherwise, we would have a contradiction. So, given that a common time slot has to overlap, the two slots have to be from different people.

A heap returns the smallest items first. Because of this time slots we remove from the heap are sorted by the start time. Taking advantage of this, we can then compare the time slots in the order of time.

Pop the first time slot out of the heap and compare it against the first element in the heap.

Figure 3. Compare the popped time slot and the top element in the heap.

Algorithm

  • Initialize a heap timeslots and push time slots that last longer than duration into it.
  • Iterate until there's only one time slot remaining in timeslots:
    • Pop the first time slot [start1, end1] from timeslots.
    • Retrieve the next time slot [start2, end2], which is the current top element in timeslots.
    • If we find end1 >= start2 + duration, because start1 <= start2, the common slot is longer than duration and we can return it.
  • If we don't find the common slot that is longer than duration, return an empty array.

Implementation

Complexity Analysis

  • Time complexity: O((M+N)log(M+N))O((M+N) \log (M+N)), when MM is the length of slots1 and NN is the length of slots2.

    There are two parts to be analyzed: 1) building up the heap; 2) the iteration when we keep popping elements from the heap. For the second part, popping one element takes O(log(M+N))O(\log(M + N)), therefore, in the worst case, popping M+NM + N elements takes O((M+N)log(M+N))O((M+N) \log (M+N)).

    Regarding the first part, we have different answers for Java and Python implementations. For Python, heapq.heapify transforms a list into a heap, in-place, in linear time; however, in Java, we choose to pop each element into the heap, which leads to a time complexity of O((M+N)log(M+N))O((M+N) \log (M+N)). Note that it is possible to convert the array into a heap in linear time using the constructor of PriorityQueue; however, that will not influence the overall time complexity and will make it less readable.

    When we put these two parts together, the total time complexity is O((M+N)log(M+N))O((M+N) \log (M+N)), which is determined by the first part.

  • Space complexity: O(M+N)O(M+N). This is because we store all M+NM+N time slots in a heap.



Report Article Issue

Comments: 5
Gift369's avatar
Read More

Thank you for the solutions! I liked the first approach.
Two pointer approach in Javascript:

var minAvailableDuration = function(slots1, slots2, duration) {
    slots1.sort((a, b) => a[0] - b[0]);
    slots2.sort((a, b) => a[0] - b[0]);
    let pointer1 = 0,
        pointer2 = 0;
    
    while (pointer1 < slots1.length && pointer2 < slots2.length) {
        let intersectStart = Math.max(slots1[pointer1][0], slots2[pointer2][0]);
        let intersectEnd = Math.min(slots1[pointer1][1], slots2[pointer2][1]);
        
        if (intersectStart + duration <= intersectEnd) {
            return [intersectStart, intersectStart + duration];
        } else if (slots1[pointer1][1] < slots2[pointer2][1]) {
            pointer1++;
        } else {
            pointer2++;
        }
    }
    return [];
};

3
Show 1 reply
Reply
Share
Report
helbendak's avatar
Read More

In the explanation for Solution 2 I believe start1<start2 (technically start1<=start2) since this is a min heap. Please let me know if you think otherwise.

1
Show 2 replies
Reply
Share
Report
hitzy's avatar
Read More

if someone comes up with second approach in interview, that would be extra bonus to come up such smart solution. Really nice solution the second one. First one was kind of conventional way one could approach after having practiced 2 pointers.

0
Reply
Share
Report
mehakwaliaC's avatar
Read More

Sweeping the time line easily understandable solution (O(nlogn)) using an ordered map.

class Solution {
public:
    vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
        // sweep the timeline
        map<int, int> avail;
        for (auto slot: slots1){
            avail[slot[0]]++;
            avail[slot[1]]--;
        }
        for (auto slot: slots2){
            avail[slot[0]]++;
            avail[slot[1]]--;
        }
        int present=0;
        vector<int> answer (2);
        for (auto pair: avail){
            present+=pair.second;
            if (present==2){
                answer[0]=pair.first;
            }
            else if (present==0 && pair.second==-2 && pair.first-answer[0]>=duration){// if both become busy
                answer[1]=answer[0]+duration;
                return answer;
            }
            else if (present==1 && pair.second==-1 && pair.first-answer[0]>=duration){// if one of them becomes busy after both being free
                answer[1]=answer[0]+duration;
                return answer;
            }
        }
        return {};
    }
};

0
Reply
Share
Report
cfchou's avatar
Read More

Why don't we sort a list instead of heapify it? I don't see much benefit of using heapq and it's slower.

0
Show 3 replies
Reply
Share
Report

You don't have any submissions yet.

1229/1883
Contribute
|||
Saved
#1201 Ugly Number III
Medium
#1202 Smallest String With Swaps
Medium
#1203 Sort Items by Groups Respecting Dependencies
Hard
#1204 Last Person to Fit in the Elevator
Medium
#1205 Monthly Transactions II
Medium
#1206 Design Skiplist
Hard
#1207 Unique Number of Occurrences
Easy
#1208 Get Equal Substrings Within Budget
Medium
#1209 Remove All Adjacent Duplicates in String II
Medium
#1210 Minimum Moves to Reach Target with Rotations
Hard
#1211 Queries Quality and Percentage
Easy
#1212 Team Scores in Football Tournament
Medium
#1213 Intersection of Three Sorted Arrays
Easy
#1214 Two Sum BSTs
Medium
#1215 Stepping Numbers
Medium
#1216 Valid Palindrome III
Hard
#1217 Minimum Cost to Move Chips to The Same Position
Easy
#1218 Longest Arithmetic Subsequence of Given Difference
Medium
#1219 Path with Maximum Gold
Medium
#1220 Count Vowels Permutation
Hard
#1221 Split a String in Balanced Strings
Easy
#1222 Queens That Can Attack the King
Medium
#1223 Dice Roll Simulation
Hard
#1224 Maximum Equal Frequency
Hard
#1225 Report Contiguous Dates
Hard
#1226 The Dining Philosophers
Medium
#1227 Airplane Seat Assignment Probability
Medium
#1228 Missing Number In Arithmetic Progression
Easy
#1229 Meeting Scheduler
Medium
#1230 Toss Strange Coins
Medium
#1231 Divide Chocolate
Hard
#1232 Check If It Is a Straight Line
Easy
#1233 Remove Sub-Folders from the Filesystem
Medium
#1234 Replace the Substring for Balanced String
Medium
#1235 Maximum Profit in Job Scheduling
Hard
#1236 Web Crawler
Medium
#1237 Find Positive Integer Solution for a Given Equation
Medium
#1238 Circular Permutation in Binary Representation
Medium
#1239 Maximum Length of a Concatenated String with Unique Characters
Medium
#1240 Tiling a Rectangle with the Fewest Squares
Hard
#1241 Number of Comments per Post
Easy
#1242 Web Crawler Multithreaded
Medium
#1243 Array Transformation
Easy
#1244 Design A Leaderboard
Medium
#1245 Tree Diameter
Medium
#1246 Palindrome Removal
Hard
#1247 Minimum Swaps to Make Strings Equal
Medium
#1248 Count Number of Nice Subarrays
Medium
#1249 Minimum Remove to Make Valid Parentheses
Medium
#1250 Check If It Is a Good Array
Hard